home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / sys / amiga / programmer / 6075 < prev    next >
Encoding:
Text File  |  1996-08-05  |  2.3 KB  |  62 lines
  1. Newsgroups: comp.sys.amiga.programmer
  2. References: <272.6650T63T1340@sn.no> <ZZNYYD.96Mar21121908@diku.dk> 
  3. X-Newsreader: MicroDot 1.8 
  4. Mime-version: 1.0
  5. Content-Type: text/plain; charset=iso-8859-1
  6. Content-Transfer-encoding: 8BIT
  7. Path: news.tng.oche.de!tomate.tng.oche.de
  8. X-Gateway: ZCONNECT UE utomate.tng.oche.de.tomate.tng.oche.de [PolyNet zTOr V4.901 Serie: "light"]
  9. Subject: Re: Sorting a list
  10. Message-ID: <xUqu7MD1A7alz7@0dietmar.tomate.tng.oche.de>
  11. Date: Fri, 22 Mar 96 12:31:39 GMT
  12. Organization: Developer
  13. X-ZC-TELEFON: +49-(0)241/81665
  14. X-ZC-POST: Mies-v-d-Rohe-Str.31 D-52074 Aachen
  15. From: DIETMAR@TOMATE.TNG.OCHE.DE (Dietmar Eilert)
  16.  
  17. zznyyd@diku.dk (Finn Nielsen) wrote:
  18.  
  19. FN> In article <314F9F68.48E2@sapiens.com> Avi Lev <avil@sapiens.com> writes:
  20. FN> > Christopher Naas wrote:
  21. FN> > > 
  22. FN> > > What's the absolutely fastest algorithm for sorting a List with around 1000
  23. FN> > > items alphabetically?
  24. FN> > > 
  25. FN> > 
  26. FN> > well, the fastest way is no doubt, bubble sort!!! but you have to perform the sort on a 
  27. FN> > list of pointers to the strings not on the strings themselves otherwise it'll be slower.
  28. FN> 
  29. FN> I really hope you're just kidding here: bubble sort is the slowest sorting
  30. FN> algorithm ever. ALTO you're right about sorting the pointers instead of the
  31. FN> [...]
  32. FN> actual strings. I recommend using QuickSort for sorting the pointers and
  33.  
  34. You could use a simple modification of bubble sort to boost performance to
  35. the speed of QuickSort: use a dynamic interval instead of comparing
  36. neighbours only. In the first pass, you would compare element <a> to
  37. element <a + distance> and swap them if the order is wrong. Distance is
  38. reduced after processing all elements. To be continued until the distance
  39. is <1> (standard bubble sort) and the order is correct.
  40.  
  41. First pass:
  42.  
  43.     distance = 3 * (elements - 1) / 4
  44.  
  45.     if (distance == 0)
  46.         distance = 1;
  47.  
  48. Next pass:
  49.  
  50.     if (distance = 3 * distance / 4)
  51.         ready = FALSE;
  52.  
  53. * In a random sampling of GoldED users, 100% said that they'd rather use
  54.   GoldED than be publically flogged, eaten alive by pirhanas, OR watch
  55.   SeaQuest DSV.
  56.  
  57. /\/\ GoldED Support: http://www.clearlight.com/~dietmar
  58. /\/\ E-Mail:         dietmar@tomate.tng.oche.de
  59. /\/\ Fileserver:     dietmar@clearlight.com (subject: send file info)
  60.      Phone/FAX:      +49-(0)241-81665-(Pause)-22
  61.  
  62.